Đền được lập từ thời Lý Thái Tông (1028-1054) ở góc phía tây nam thành Thăng Long cũ thuộc địa phận làng Thủ Lệ nay là công viên Thủ Lệ. Thờ hoàng tử Linh Lang, con của vua Lý Thái Tông, và bà phi thứ 9 Dương Thị Quang, nhưng tương truyền vốn là con của Long Quân, tên gọi là Hoàng Châu, thác sinh, là người có công trong cuộc kháng chiến chống quân xâm lược nhà Tống, và đã hi sinh trên phòng tuyến sông Cầu vào năm 1076.

Sau khi mất, được người dân Thủ Lệ lập đền thờ và được nhà vua sắc phong là Linh Lang đại vương thượng đẳng phúc thần. Thần đã nhiều lần âm phù giúp nhà Trần trong cuộc chiến chống quân xâm lược Nguyên - Mông, và nhà Lê trong cuộc phục hưng. Vì trước cửa đền có đắp hai con voi quỳ gối nên quen gọi là đền Voi Phục và vì đền ở phía tây kinh thành nên còn gọi là trấn Tây hoặc trấn Đoài (Đoài, theo bát quái thuộc phương Tây).

Đền Voi Phục hiện nay nằm tại phường Ngọc Khánh, quận Ba Đình, Hà Nội. Đền còn được gọi là Đền Voi Phục Thủ Lệ để phân biệt với Đền Voi Phục Thụy Khuê tại số 251 đường Thụy Khuê, quận Tây Hồ, Hà Nội. Trước đây, đền nằm trong hệ Tứ Trấn, "giữ" phía Tây kinh thành. Nơi đây vốn là đất lắm hồ ao, lầy lội, là một trong Thập tam trại có từ thời Lý. Đương thời, thuộc tổng nội, huyện Quảng Đức, phủ Phụng Thiên.

Tương truyền, đền Voi Phục được xây dựng năm Chương Thánh Gia Khánh thứ 7 (năm 1065) đời vua Lý Thánh Tông trên một khu gò cao thuộc vùng đất của trại Thủ Lệ -một trong 13 làng trại ở phía tây kinh thành Thăng Long. Mở đầu cho đền, hiện nay là cổng tứ trụ, như những trục vũ trụ đem sinh khí từ tầng trên truyền xuống trần gian (đây là sản phẩm của thế kỷ XIX - XX), hai bên cổng có bia hạ mã và đôi voi chầu phục (hiện mới được xây thêm nghi môn tứ trụ nữa, ở sát với đường lớn). Cũng chính vì điều này mà đền mang tên Voi Phục.